package leetcode.jianzhioffer;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-27 17:03
 **/
public class JianZhiOffer04 {

    /*public boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int i1 = 0; i1 < matrix[i].length; i1++) {
                if (matrix[i][i1] == target) {
                    return true;
                }
            }
        }
        return false;
    }*/

    /*public boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            int low = 0;
            int high = matrix[i].length - 1;
            while (low <= high) {
                int avg = low + high >> 1;
                if (matrix[i][avg] == target) {
                    return true;
                } else if (matrix[i][avg] > target) {
                    high = avg - 1;
                } else {
                    low = avg + 1;
                }
            }
        }
        return false;
    }*/

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //剑指offer版排除特殊情况
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        //总行数和总列数
        int rows = matrix.length;
        int columns = matrix[0].length;
        //右上角坐标
        int x = 0;
        int y = columns - 1;
        while (x < rows && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] > target) {
                y--;
            } else {
                x++;
            }
        }
        return false;
    }

}
